package linkList;

import java.util.HashMap;

// import linkList.LRUCache.ListNode;

public class LRUCache {
    // int count = 0;
    // int capacity = 0;
    // // 定义内部类Node
    // ListNode head = null;
    // HashMap<Integer, ListNode> map = new HashMap<>();

    // public static class ListNode {
    //     public int value;
    //     public int key;
    //     public ListNode next;
    //     public ListNode pre;

    //     ListNode() {
    //     }

    //     ListNode(int value, int key) {
    //         this.value = value;
    //         this.key = key;
    //     }

    //     public ListNode(int value, int key, ListNode next, ListNode pre) {
    //         this.value = value;
    //         this.key = key;
    //         this.next = next;
    //         this.pre = pre;
    //     }
    // }

    // public LRUCache(int capacity) {
    //     this.capacity = capacity;
    // }

    // public int get(int key) {
    //     if (map.containsKey(key)) {
    //         // 更新位置
    //         ListNode node = map.get(key);
    //         ListNode pre = node.pre, next = node.next;
    //         // 成环了

    //         // 更新头尾
    //         // 不为头尾
    //         if (node == head) {
    //             // 无需操作

    //         } else if (node == head.pre) {
    //             head = head.pre;
    //         } else {
    //             // 中间还有一个节点才需要
    //             // if (pre != next) {
    //             pre.next = next;
    //             next.pre = pre;
    //             // }
    //             pre = head.pre;
    //             pre.next = node;
    //             node.pre = pre;
    //             node.next = head;
    //             head.pre = node;
    //             head = node;
    //         }
    //         return node.value;
    //     } else {
    //         return -1;
    //     }

    // }

    // public void put(int key, int value) {
    //     if (map.containsKey(key)) {
    //         ListNode node = map.get(key);
    //         node.value = value;
    //         // update map
    //         map.put(key, node);
    //         // update position
    //         ListNode pre = node.pre, next = node.next;
    //         if (node == head) {
    //             // 无需操作
    //         } else if (node == head.pre) {
    //             head = head.pre;
    //         } else {
    //             // 中间还有一个节点才需要
    //             // if (pre != next) {
    //             pre.next = next;
    //             next.pre = pre;
    //             // }
    //             pre = head.pre;
    //             pre.next = node;
    //             node.pre = pre;
    //             node.next = head;
    //             head.pre = node;
    //             head = node;
    //         }
    //     } else {
    //         if (count < capacity) {
    //             count++;
    //             // 头插法
    //             ListNode node = new ListNode(value, key);
    //             if (head == null) {
    //                 head = node;
    //                 head.next = head;
    //                 head.pre = head;
    //             } else {
    //                 ListNode pre = head.pre;
    //                 pre.next = node;
    //                 node.pre = pre;
    //                 node.next = head;
    //                 head.pre = node;
    //                 head = node;
    //             }
    //             // update map
    //             map.put(key, node);
    //         } else {
    //             // 淘汰最老的
    //             // 1 2 3 4 5 > 5 1 2 3 4

    //             head = head.pre;
    //             // update map
    //             map.remove(head.key);
    //             head.value = value;
    //             head.key = key;
    //             map.put(key, head);
    //         }
    //     }

    // }
class Node{
        int val=0;
        int key=0;
        Node pre=null;
        Node next=null;
        public Node(int k,int value,Node p,Node n){
            key=k;
            val=value;
            pre=p;
            next=n;
        }
        public Node(int value,int k){
            val=value;
            key=k;
        }
    }
    int count=0,capacity=0;
    Node head=null;
    HashMap<Integer,Node> map =new HashMap<>();
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            Node node=map.get(key);
            //分类讨论
            //更新位置
            Node nodePre=node.pre,nodeNext=node.next;
            Node headPre=head.pre;
            if(node==head){
                return head.val;
            }else if(node==headPre){
                head=headPre;
                return head.val;
            }
            nodePre.next=nodeNext;
            nodeNext.pre=nodePre;
            
            headPre.next=node;
            node.pre=headPre;
            head.pre=node;
            node.next=head;
            head=node;
            //更新map
            map.put(key,node);
            return node.val;
        }else{
            return -1;
        }
    }
    
    public  void put(int key, int value) {
        //先判断是否存在，是则更新
        if(map.containsKey(key)){
            //更新值，同时更新位置
            Node node = map.get(key);
            node.val=value;
            
            Node headPre=head.pre;
            if(node==head){
                return ;
            }else if(node==headPre){
                head=headPre;
                return ;
            }
            Node nodePre=node.pre,nodeNext=node.next;
            nodePre.next=nodeNext;
            nodeNext.pre=nodePre;
            
            headPre.next=node;
            node.pre=headPre;
            head.pre=node;
            node.next=head;
            head=node;
            map.put(key,node);
        }else{
            //判断容量
            if(count<capacity){
                Node newNode = new Node(value,key);
                
                if(head==null){
                    newNode.next=newNode;
                    newNode.pre=newNode;
                    head=newNode;
                }else{
                    Node headPre=head.pre;
                    headPre.next=newNode;
                    newNode.pre=headPre;
                    newNode.next=head;
                    head.pre=newNode;
                    head=newNode;
                }
                map.put(key,newNode);
                
            }else{
                //更新map中的尾节点
                Node headPre=head.pre;
                int oldKey=headPre.key;
                map.remove(oldKey);
                head=headPre;
                head.key=key;
                head.val=value;
                map.put(key,head);
            }
        }
    }
    public static void main(String[] args) {
        int capacity=2;
        LRUCache lru = new LRUCache(capacity);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1));
        lru.put(3, 3);
        System.out.println(lru.get(2));
        lru.put(4, 4);
        System.out.println(lru.get(1));
        System.out.println(lru.get(3));
        System.out.println(lru.get(4));

        // int capacity = 1;
        // LRUCache lru = new LRUCache(capacity);
        // lru.put(2, 1);
        // System.out.println(lru.get(2));
        // lru.put(3, 2);
        // System.out.println(lru.get(2));
        // System.out.println(lru.get(3));

        // int capacity = 2;
        // LRUCache lru = new LRUCache(capacity);
        // lru.put(2, 1);
        // lru.put(2, 2);
        // System.out.println(lru.get(2));
        // lru.put(1, 1);
        // lru.put(4, 1);
        // System.out.println(lru.get(2));

        // int capacity = 2;
        // LRUCache lru = new LRUCache(capacity);
        // System.out.println(lru.get(2));
        // lru.put(2, 6);
        // System.out.println(lru.get(1));
        // lru.put(1, 5);
        // lru.put(1, 2);
        // System.out.println(lru.get(1));
        // System.out.println(lru.get(2));

        // int capacity = 2;
        // LRUCache lru = new LRUCache(capacity);
        // lru.put(2, 1);
        // lru.put(3, 2);
        // System.out.println(lru.get(3));
        // System.out.println(lru.get(2));
        // lru.put(4, 3);
        // System.out.println(lru.get(2));
        // System.out.println(lru.get(3));
        // System.out.println(lru.get(4));

        // int capacity = 3;
        // LRUCache lru = new LRUCache(capacity);
        // lru.put(1, 1);
        // lru.put(2, 2);
        // lru.put(3, 3);
        // lru.put(4, 4);
        // System.out.println(lru.get(4));
        // System.out.println(lru.get(3));
        // System.out.println(lru.get(2));
        // System.out.println(lru.get(1));
        // lru.put(5, 5);
        // System.out.println(lru.get(1));
        // System.out.println(lru.get(2));
        // System.out.println(lru.get(3));
        // System.out.println(lru.get(4));
        // System.out.println(lru.get(5));
    }
}
